package algorithm.offer;

import java.util.HashSet;
import java.util.Set;

public class Offer_38_permutation {
    public static String[] permutation(String s) {
        Set<String> list = new HashSet<>();
        char[] arrChars = s.toCharArray();
        boolean[] visit = new boolean[arrChars.length];
        //递归实现
        dfs(arrChars, "", visit, list);
        return list.toArray(new String[0]);
    }

    public static void dfs(char[] arrChars, String item, boolean[] visit, Set<String> list) {
        if (item.length() == arrChars.length) {
            list.add(item);
            return;
        }
        for (int i = 0; i < arrChars.length; i++) {
            if (visit[i]) {
                //若已经使用过则跳过
                continue;
            }
            //以下开始dfs
            visit[i] = true;
            dfs(arrChars, item + arrChars[i], visit, list);
            visit[i] = false;
        }
    }

    public static void main(String[] args) {
        String[] res = permutation("abc");
        for (String item : res) {
            System.out.println(item);
        }
    }
}
